// https://leetcode.cn/problems/dungeon-game/

// 题干：恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。
//      地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
//      骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
//      有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；
//      其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
//      为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。
//      返回确保骑士能够拯救到公主所需的最低初始健康点数。
//      注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

// 示例：输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
//      输出：7

// 碎语：

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon)
    {
        // 状态表示
        // 经验 + 题目要求

        // 1.以某个位置为结尾。。。
        // 2.以某个位置为起点。。。
        // dp[i][j]表示从起点出发，到达i,j位置的时候，所需的最初健康点数不可行，会受到后续路径选择的影响
        // 以某个位置为起点，巴拉巴拉
        // dp[i][j]表示从i,j位置出发，到达终点，所需要的最低初试健康点数
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));

        dp[m][n - 1] = dp[m - 1][n] = 1;
        for (int i = m - 1 ; i >= 0 ; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = max(1, dp[i][j]);
            }
        }

        return dp[0][0];
    }
};

int main()
{
    Solution sol;
    vector<vector<int>> dungeon = {{-2,-3,3},{-5,-10,1},{10,30,-5}};

    cout << sol.calculateMinimumHP(dungeon) << endl;
    
    return 0;
}